1. Field of the Invention
The invention relates generally to the graphical display of information and more particularly to the graphical display of information which can be represented as a graph consisting of nodes and edges.
2. Description of the Prior Art
Graphs made up of nodes and edges have long been used to represent entities and a relationship between them. For example, a telephone call from a caller to a callee may be represented by two nodes, one representing the caller and the other the callee, and an edge which connects the nodes and represents the call.
With the advent of digital computer systems with sufficient power to drive large high-resolution displays, graphs began to be used to visually represent information accessible to the computer system on displays. Moreover, users of the computer systems could use input devices such as a mouse or a keyboard to interact with the displayed graphs. In many cases, the input device could move a pointer in the display, and the interaction with the graphs depended on the location of the pointer in the display.
One example of an interactive display system which employs graphs is the system disclosed in U.S. Pat. No. 5, 136,690, Becker et al., Dynamic Graphical Analysis of Network Data, issued Aug. 4, 1992. FIG. 6 herein is FIG. 2 of that patent. As shown in FIG. 6, the display of that system has a map 600 of the continental United States upon which nodes are displayed which represent AT&T's switching centers. The edges connecting the nodes represent various statistics concerning the flow of traffic between the nodes. In FIG. 6, edge 603 can be seen connecting nodes 601 and 602. The edges in the figure represent blocked calls between the nodes. FIG. 6 shows blocked calls immediately after a serious earthquake in California.
As is immediately apparent from FIG. 6, a major problem of displays like those of FIG. 6 is clutter, that is, the tendency of the display to become unreadable as the amount of data it displays increases. Thus, in FIG. 6, the sheer volume of blocked calls results in so many edges 603 in the display that large portions of the display are hidden and individual edges cannot be distinguished. Another example of the same problem may be found in Michael F. Schwartz and David C. M. Wood, "Discovering Shared Interests using Graph Analysis", in: Communications of the ACM, Vol. 36, no. 8, August 1993, pp. 78-89. See in particular FIG. 3.
To deal with the problem of clutter, Becker's system includes controls which permit the user to interactively modify the display to reduce clutter. The controls are operated by using a pointing device such as a mouse to move a pointer 640 in the display to the control and then using a button on the mouse to specify an action.
The first of these controls is slider 606, which the user can employ to reduce clutter by interactively increasing or decreasing the portions of edges 603 which are actually displayed. At the "short" extreme, no edges 603 are shown; at the "long" extreme, the entire length of each edge 603 is shown. At intermediate positions, a part of the middle portion of each edge is not shown, with the amount not shown being proportional to the position of the slider.
Slider 610 relates data values to colors and also permits the user to reduce clutter by interactively establishing display thresholds. Slider 610 is divided into different-colored areas (area 651, for example), each one of which represents a range of the values represented by the edges. Edges representing values which fall within a color's range are displayed in that color. The user may interactively define an upper threshold, a lower threshold, or both in slider 610. Only those edges 603 are displayed whose values lie below the upper threshold (if there is one) and above the lower threshold (if there is one).
Users may further reduce clutter by deactivating nodes. This is done by using the mouse to move the pointer to a node and then depressing a button on the mouse. The node is displayed in a different color and the edges connecting the node to the other nodes are not displayed. The user may reactivate an inactive node in the same fashion.
Buttons in the lower right-hand corner of FIG. 6, finally, permit the user to "zoom" into or out of an area of the display, to extend an edge 603 which is not being completely displayed, and to toggle between a display of the presently-active nodes and a display of the presently-inactive nodes.